package com.yiwenup.leetcode.site;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @PROJECT struct-algorithm
 * @PACKAGE com.yiwenup.leetcode.site
 * @Author yiwenup
 * @Date 2022-03-14 20:05:45
 * <p>
 * @DESCRIPTION https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/
 */
public class No0599 {

    /**
     * 执行用时：5 ms, 在所有 Java 提交中击败了99.63%的用户
     * 内存消耗：41.8 MB, 在所有 Java 提交中击败了35.78%的用户
     */
    public String[] findRestaurant(String[] list1, String[] list2) {
        if (list1.length > list2.length) return findRestaurant(list2, list1);

        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            map.put(list1[i], i);
        }

        List<String> res = new ArrayList<>();
        int sumIdx = Integer.MAX_VALUE;
        for (int i = 0; i < list2.length && i <= sumIdx; i++) {
            if (map.containsKey(list2[i])) {
                int sum = map.get(list2[i]) + i;
                if (sum < sumIdx) {
                    res.clear();
                    res.add(list2[i]);
                    sumIdx = sum;
                } else if (sum == sumIdx) {
                    res.add(list2[i]);
                }
            }
        }

        return res.toArray(new String[]{});
    }

    /**
     * 执行用时：98 ms, 在所有 Java 提交中击败了15.14%的用户
     * 内存消耗：42.1 MB, 在所有 Java 提交中击败了9.91%的用户
     */
    public String[] findRestaurant1(String[] list1, String[] list2) {
        List<String> list = new ArrayList<>();

        int sumIdx = Integer.MAX_VALUE;
        for (int i = 0; i < list1.length; i++) {
            for (int j = 0; j < list2.length; j++) {
                if (list2[j].equals(list1[i])) {
                    int sum = i + j;
                    if (sum < sumIdx) {
                        sumIdx = sum;
                        list.clear();
                        list.add(list1[i]);
                    } else if (sum == sumIdx) {
                        list.add(list1[i]);
                    }
                }
            }
        }

        return list.toArray(new String[]{});
    }
}
